﻿#include <iostream>
#include <stack>
#include <vector>

using namespace std;

class Solution
{
public:
    // 394. 字符串解码
    string decodeString(string s)
    {
        stack<string> sst;
        stack<int> nst;
        sst.push("");
        int i = 0;
        while (i < s.size())
        {
            if (s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while (s[i] >= '0' && s[i] <= '9')
                {
                    tmp = tmp * 10 + (s[i] - '0');
                    i++;
                }
                nst.push(tmp);
            }
            else if (s[i] == '[')
            {
                i++;
                string tmp;
                while (s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i];
                    i++;
                }
                sst.push(tmp);
            }
            else if (s[i] == ']')
            {
                int t = nst.top();
                nst.pop();
                string st = sst.top();
                sst.pop();
                while (t--)
                {
                    sst.top() += st;
                }
                i++;
            }
            else
            {
                string tmp;
                while (i < s.size() && s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i];
                    i++;
                }
                sst.top() += tmp;
            }
        }
        return sst.top();
    }

    // 946. 验证栈序列
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped)
    {
        int popi = 0;
        stack<int> st;
        for (auto x : pushed)
        {
            st.push(x);
            while (st.size() && st.top() == popped[popi])
            {
                st.pop();
                popi++;
            }
        }
        return popi == popped.size();
    }
};

int main()
{
    /*string s = "abc3[cd]xyz";
    cout << Solution().decodeString(s) << endl;*/

    vector<int> pushed = { 1,0 };
    vector<int> poped = { 1,0 };
    cout << Solution().validateStackSequences(pushed, poped) << endl;

    return 0;
}